package com.mj.listen3.链表;

public class _0_链表按某值划分左小_中等_右大 {

    // 进阶解法2 不使用虚拟头节点
    public static ListNode listPartition3(ListNode head, int pivot) {
        if (head == null) return head;
        ListNode sH = null, sT = null, eH = null, eT = null, bH = null, bT = null;
        while (head != null) {
            ListNode temp = head.next;
            head.next = null;
            if (head.val < pivot) {
                if (sH == null) {
                    // 该链表头一次添加元素
                    sH = head;
                    sT = head;
                } else {
                    sT.next = head;
                    // 尾巴指针往下移动
                    sT = sT.next;
                }
            } else if (head.val == pivot) {
                if (eH == null) {
                    // 该链表头一次添加元素
                    eH = head;
                    eT = head;
                } else {
                    eT.next = head;
                    eT = eT.next;
                }
            } else {
                if (bH == null) {
                    // 该链表头一次添加元素
                    bH = head;
                    bT = head;
                } else {
                    bT.next = head;
                    bT = bT.next;
                }
            }

            // head指针往下移动
            head = temp;
        }

        // 重新连接链表

        // 连接小和中链表
        if (sT != null) {
            sT.next = eH;
            eT = eT != null ? eT : sT;
        }

        // 连接所有链表
        if (eT != null) {
            eT.next = bH;
        }

        // 返回头节点。要判断三段链表是否为空
        return sH != null ? sH : eH != null ? eH : bH;
    }

    // 进阶解法
    public static ListNode listPartition2(ListNode head, int pivot) {
        if (head == null) return head;
        ListNode small = new ListNode(0);
        ListNode equals = new ListNode(0);
        ListNode big = new ListNode(0);
        ListNode sE = small;
        ListNode eE = equals;
        ListNode bE = big;

        while (head != null) {
            ListNode temp = head.next;
            // 要把head指针指向的节点的next指针置位空，否则默认的next就不会被清掉
            head.next = null;
            if (head.val < pivot) {
                // 往 small 链表中连接
                sE.next = head;
                sE = sE.next;
            } else if (head.val == pivot) {
                // 往equal链表中连接
                eE.next = head;
                eE = eE.next;
            } else {
                // 往big链表中连接
                bE.next = head;
                bE = bE.next;
            }

            // head指针往下走
            head = temp;
        }

        // 连接链表
        // 小的和相等的重新连接
        if (small != sE) {
            sE.next = equals.next;
            // 中间链表是否为空，为空的话变为small的尾节点
            eE = eE == equals ? sE : eE;
        }

        // 连接大于的
        if (eE != equals) {
            eE.next = big.next;
        }


        return small.next != null ? small.next : equals.next != null ? equals.next : big.next;
    }

    // 笨解法
    public ListNode listPartition1(ListNode head, int pivot) {
        if (head == null) return head;
        // 1.遍历一遍，求出链表的长度
        ListNode cur = head;
        int len = 0;
        while (cur != null) {
            cur = cur.next;
            len++;
        }

        // 2.创建一个长度为len的数组
        ListNode[] nodeArr = new ListNode[len];

        // 3.把所有的节点依次都放置到数组中去
        cur = head;
        for (int i = 0; i < nodeArr.length; i++) {
            nodeArr[i] = cur;
            cur = cur.next;
        }

        // 4.对数组内的元素进行 Partition 操作
        arrPartition(nodeArr, pivot);

        // 5.将数组中的节点依次连接成新的链表
        for (int i = 1; i < nodeArr.length; i++) {
            nodeArr[i - 1].next = nodeArr[i];
        }

        // 最后一个节点的 next 置位 null
        nodeArr[len - 1].next = null;

        return nodeArr[0];// 0位置就是新的头节点
    }

    private void arrPartition(ListNode[] nodeArr, int pivot) {
        // 使用三个指针
        int li = 0;
        int re = nodeArr.length - 1;
        int ai = 0;
        // 开始 Partition
        while (ai > re) {// 结束遍历
            if (nodeArr[ai].val < pivot) {
                // 与li位置的元素交换，li和ai指针都往后走一步
                swap(nodeArr, li++, ai++);
            } else if (nodeArr[ai].val == pivot) {
                // ai指针往后走
                ai++;
            } else {
                // 与re位置的元素交换，re的指针往前走一步，ai的指针不动。因为交换回来的数值可能小于pivot也可能大于pivot
                swap(nodeArr, re--, ai);
            }
        }
    }

    // 交换 i 和 j 位置的元素
    private void swap(ListNode[] nodeArr, int i, int j) {
        ListNode temp = nodeArr[i];
        nodeArr[i] = nodeArr[j];
        nodeArr[j] = temp;
    }
}
